// FILE: BinTree.h
// PROVIDES: A template class for a node in a binary tree and
// functions (toolkit) for manipulating binary trees. The template
// parameter is the type of data in each node.
//
// TYPEDEF for the binary_tree_node<Item> template class:
//   Each node of the tree contains a piece of data and pointers to
//   its children. The type of the data
//   (binary_tree_node<Item>::value_type) is the Item type from the
//   template parameter. The type may be any of the C++ built-in
//   types (int, char, etc.), or a class with a default constructor,
//   and an assignment operator.
//
// CONSTRUCTOR for the binary_tree_node<Item> class:
//   binary_tree_node(
//       const item& init_data = Item(),
//       binary_tree_node<Item>* init_left = 0,
//       binary_tree_node<Item>* init_right = 0
//   )
//     Precondition: (none)
//     Postcondition: The new node has its data equal to init_data,
//     and it's child pointers equal to init_left and init_right.
//
// MEMBER FUNCTIONS for the binary_tree_node<Item> class:
// ------------------------------------------------------
// NOTE: The return values from the non-const versions of the left()
// and right() functions have been changed (compared to those shown
// in earlier printings of the textbook) so that they each return a
// reference to the pointer in the node. This is indicated by the &
// symbol here:
//   binary_tree_node*& left()
// The use of a "reference" in the return value has two advantages
// that simplify implementations involving binary trees:
// 1. It now allows a direct assignment such as: p->left() = 0.
//    This is not a huge advantage since the same thing can be
//    accomplished by using the set_left function.
// 2. The expression p->left() can be passed as the argument
//    to a function such as: tree_clear( p->left() );
//    The parameter of tree_clear is a reference parameter, so that
//    any changes that tree_clear makes to p->left() will now effect
//    the actual left pointer in the node *p. In this example, the
//    tree_clear function does set its parameter to 0, so that the
//    total effect of tree_clear(p->left()) is to clear the left
//    subtree of p and to set p's left pointer to 0.
//    In the case of tree_clear, this is not a huge advantage
//    because we could have just set p's left pointer to 0
//    ourselves. But, the discussions of binary search trees in the
//    textbook involve 2 functions, bst_remove and bst_remove_max,
//    which are easier to write if p->left() and p->right() can be
//    passed as reference parameters in the recursive calls.
// ------------------------------------------------------
//   const item& data() const      <----- const version
//   and
//   Item& data()                  <----- non-const version
//     Precondition: (none)
//     Postcondition: The return value is a reference to the data
//     from this binary_tree_node.
//
//   const binary_tree_node* left() const  <----- const version
//   and
//   binary_tree_node*& left()             <----- non-const version
//   and
//   const binary_tree_node* right() const <----- const version
//   and
//   binary_tree_node*& right()            <----- non-const version
//     Precondition: (none)
//     Postcondition: The return value is a pointer to the left or
//     right child (which will be 0 if there is no child).
//
//   void set_data(const Item& new_data)
//     Precondition: (none)
//     Postcondition: The binary_tree_node now contains the
//     specified new data.
//
//   void set_left(binary_tree_node* new_link)
//   and
//   void set_right(binary_tree_node* new_link)
//     Precondition: (none)
//     Postcondition: The binary_tree_node now contains the
//     specified new link to a child.
//
//   bool is_leaf()
//     Precondition: (none)
//     Postcondition: The return value is true if the node is a
//     leaf; otherwise the return value is false.
//
// NON-MEMBER FUNCTIONS (toolkit) to maniplulate binary tree nodes:
//   tempate <class Process, class BTNode>
//   void inorder(Process f, BTNode* node_ptr)
//     Precondition: node_ptr is a pointer to a node in a binary
//     tree (or node_ptr may be 0 to indicate the empty tree).
//     Postcondition: If node_ptr is not 0, then the function
//     f has been applied to the contents of *node_ptr and all of
//     its descendants, using an in-order traversal.
//     Note: BTNode may be a binary_tree_node or a const binary
//     tree node. Process is the type of a function f that may be
//     called with a single Item argument (using the Item type from
//     the node).
//
//   tempate <class Process, class BTNode>
//   void postorder(Process f, BTNode* node_ptr)
//      Same as the in-order function, except with a post-order
//      traversal.
//
//   tempate <class Process, class BTNode>
//   void preorder(Process f, BTNode* node_ptr)
//      Same as the in-order function, except with a pre-order
//      traversal.
//
//   template <class Item, class SizeType>
//   void print(const binary_tree_node<Item>* node_ptr,
//              SizeType depth)
//     Precondition: node_ptr is a pointer to a node in a binary
//     tree (or node_ptr may be 0 to indicate the empty tree). If
//     the pointer is not 0, then depth is the depth of the node
//     pointed to by node_ptr.
//     Postcondition: If node_ptr is not 0, then the contents of
//     *node_ptr and all its descendants have been written to cout
//     with the << operator, using a backward in-order traversal.
//     Each node is indented four times its depth.
//
//   template <class Item>
//   void tree_clear(binary_tree_node<Item>*& root_ptr)
//     Precondition: root_ptr is the root pointer of a binary
//     tree (which may be 0 for the empty tree).
//     Postcondition: All nodes at the root or below have been
//     returned to the heap, and root_ptr has been set to 0.
//
//   template <class Item>
//   binary_tree_node<Item>*
//   tree_copy(const binary_tree_node<Item>* root_ptr)
//     Precondition: root_ptr is the root pointer of a binary tree
//     (which may be 0 for the empty tree).
//     Postcondition: A copy of the binary tree has been made, and
//     the return value is a pointer to the root of this copy.
//
//   template <class Item>
//   size_t tree_size(const binary_tree_node<Item>* node_ptr)
//     Precondition: node_ptr is a pointer to a node in a binary
//     tree (or node_ptr may be 0 to indicate the empty tree).
//     Postcondition: The return value is the number of nodes in
//     the tree.

#ifndef BINTREE_H
#define BINTREE_H
#include <cstdlib>  // provides size_t

namespace cs3358Spring2007Assign08
{
   template <class Item>
   class binary_tree_node
   {
   public:
   	// TYPEDEF
	   typedef Item value_type;
   	// CONSTRUCTOR
	   binary_tree_node(const Item& init_data = Item(),
	                    binary_tree_node* init_left = 0,
	                    binary_tree_node* init_right = 0);
      // MODIFICATION MEMBER FUNCTIONS
	   Item& data();
   	binary_tree_node*& left();
	   binary_tree_node*& right();
   	void set_data(const Item& new_data);
	   void set_left(binary_tree_node* new_left);
   	void set_right(binary_tree_node* new_right);
	   // CONST MEMBER FUNCTIONS
	   const Item& data() const;
	   const binary_tree_node* left() const;
   	const binary_tree_node* right() const;
	   bool is_leaf() const;
   private:
   	Item data_field;
	   binary_tree_node *left_field;
   	binary_tree_node *right_field;
   };

   // NON-MEMBER (TOOLKIT) FUNCTIONS for the binary_tree_node<Item>:
   template <class Process, class BTNode>
   void inorder(Process f, BTNode* node_ptr);

   template <class Process, class BTNode>
   void preorder(Process f, BTNode* node_ptr);

   template <class Process, class BTNode>
   void postorder(Process f, BTNode* node_ptr);

   template <class Item, class SizeType>
   void print(const binary_tree_node<Item>* node_ptr,
              SizeType depth);

   template <class Item>
   void tree_clear(binary_tree_node<Item>*& root_ptr);

   template <class Item>
   binary_tree_node<Item>* tree_copy(
      const binary_tree_node<Item>* root_ptr);

   template <class Item>
   size_t tree_size(const binary_tree_node<Item>* node_ptr);
}

#include "BinTree.template"

#endif
